package com.heima.leetcode.algorithm.sort;

import java.util.Arrays;

/**
 * <strong>按照元素在数组中出现频率升序排序，如果频率相同，则按照值降序排序 1636</strong>
 * <p>条件：数组元素在-100到100之间</p>
 *
 * @author 勾新杰
 * @version 1.0
 * @date 2024/10/6 22:45
 */
public class FrequencySort {

    /**
     * <h3>方法一</h3>
     * 按照元素在数组中出现频率升序排序，如果频率相同，则按照值降序排序
     * @param nums 待排序的数组
     * @return 排序后的数组
     */
    public static int[] frequencySort1(int[] nums) {
        // 创建一个count数组，记录数组中每个元素的出现次数
        int[] count = new int[201];
        // 遍历nums数组，对count数组进行赋值
        for (int i : nums) {
            count[i + 100]++;
        }
        // 简单的方法就是定义一个比较器对数组进行排序
        return Arrays.stream(nums).boxed().sorted((o1, o2) -> {
                    int o1f = count[o1 + 100];
                    int o2f = count[o2 + 100];
                    // 频率升序排
                    if (o1f > o2f) {
                        return 1;
                    } else if (o1f < o2f) {
                        return -1;
                    } else {
                        // 频率相同，值降序排
                        return o2 - o1;
                    }
                }
        ).mapToInt(Integer::intValue).toArray();
    }

    /**
     * <h3>方法二</h3>
     * 按照元素在数组中出现频率升序排序，如果频率相同，则按照值降序排序
     * @param nums 待排序的数组
     * @return 排序后的数组
     */
    public static int[] frequencySort2(int[] nums) {
        // 创建一个count数组，记录数组中每个元素的出现次数
        int[] count = new int[201];
        // 遍历nums数组，对count数组进行赋值，并且找出最大频率
        int maxcount = 0;
        for (int i : nums) {
            count[i + 100]++;
            if (count[i + 100] > maxcount) {
                maxcount = count[i + 100];
            }
        }
        // 遍历count数组，生成排序好的数组
        int index = 0;
        // 优先按照频率升序
        for (int i = 1; i <= maxcount; i++) {
            // 从后往前遍历，就可以做到频率相同时，值降序排序
            for (int j = count.length - 1; j >= 0; j--) {
                if (count[j] == i) {
                    while (count[j]-- > 0) {
                        nums[index++] = j - 100;
                    }
                }
            }
        }
        return nums;
    }
}
